#ifndef BTL_MATHS_ONLINESTATISTICS
#define BTL_MATHS_ONLINESTATISTICS

#include <cmath>
#include <iosfwd>

namespace btl
{
namespace maths
{

/// Computes a running mean and variance value for a data series.
///
/// Note that this is actually more numerically stable than the
/// obvious two-pass offline algorithm.
///
/// For more information, see
///   http://www.johndcook.com/standard_deviation.html
/// or Knuth's Art of Computer Programming, Vol 2, page 232, 3rd edition.
class OnlineStatistics
{
   public:
      OnlineStatistics();

      void push(double x);

      double mean() const;
      double sampleVar() const;
      double sampleStdDev() const;
      double populationVar() const;
      double populationStdDev() const;
      unsigned long long count() const;
   private:
      double _m;
      double _s;
      unsigned long long _n;
};

std::ostream& operator<<(std::ostream& ss, const OnlineStatistics& stats);

} // namespace maths
} // namespace btl

// ====================================================================
// === Implementation

namespace btl
{
namespace maths
{

inline OnlineStatistics::OnlineStatistics():
   _m(0.0), _s(0.0), _n(0) {}

inline void OnlineStatistics::push(double x)
{
   ++_n;
   if(_n > 1)
   {
      double m0 = _m, s0 = _s;
      _m = m0 + (x - m0) / _n;
      _s = s0 + (x - m0) * (x - _m);
   }
   else
      _m = x;
}

inline double OnlineStatistics::mean() const
{
   return _m;
}

inline double OnlineStatistics::sampleVar() const
{
   return (_n > 1) ? _s / (_n - 1) : 0.0;
}

inline double OnlineStatistics::sampleStdDev() const
{
   return std::sqrt(sampleVar());
}

inline double OnlineStatistics::populationVar() const
{
   return (_n > 1) ? _s / _n : 0.0;
}

inline double OnlineStatistics::populationStdDev() const
{
   return std::sqrt(populationVar());
}

inline unsigned long long OnlineStatistics::count() const
{
   return _n;
}

} // namespace maths
} // namespace btl

#endif // BTL_MATHS_ONLINESTATISTICS
